package LinkedList;
/**
 *给定一个奇数位升序，偶数位降序的链表，将其重新排序。
 *
 * 输入: 1->8->3->6->5->4->7->2->NULL
 * 输出: 1->2->3->4->5->6->7->8->NULL
 *
 * */
public class 排序奇升偶降链表 {

    public static ListNode Sorting_Ascending_Descending_List(ListNode head){
        if(head==null || head.next == null){
            return head;
        }
        //首先将链表按奇偶拆成两个链表
        ListNode oddHead = new ListNode(0);
        ListNode evenHead = new ListNode(0);
        ListNode oh = oddHead;
        ListNode eh = evenHead;

        ListNode even = head.next;
        ListNode odd = head;
        while(even!=null && even.next!=null){
            oh.next = odd;
            eh.next = even;

            odd = even.next;
            even = even.next.next;

            oh = oh.next;
            oh.next = null;

            eh = eh.next;
            eh.next = null;

        }
        if(even!=null){
            eh.next = even;
        }
        if(odd!=null){
            oh.next = odd;
            oh = oh.next;
            oh.next = null;
        }

        //反转偶数链表
        ListNode reverseEven = reverse(evenHead.next);
        //合并两个链表
        return merge(oddHead.next,reverseEven);
    }

    //按升序合并两个链表
    private static ListNode merge(ListNode l,ListNode r){
        ListNode tmp = new ListNode(0);
        ListNode res = tmp;

        while(l!=null && r!=null){
            if(l.val>r.val){
                tmp.next = r;
                r = r.next;
            }else{
                tmp.next = l;
                l = l.next;
            }
            tmp = tmp.next;
        }

        tmp.next = l==null ? r : l ;
        return res.next;
    }

    //反转链表
    private static ListNode reverse(ListNode node){
        ListNode pre = null;
        ListNode curr = node;

        while(curr!=null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }

        return pre;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        ListNode node1 = new ListNode(8);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(6);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(7);
        ListNode node7 = new ListNode(2);
        ListNode node8 = new ListNode(9);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        ListNode listNode = Sorting_Ascending_Descending_List(node);
        while(listNode!=null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
